package Point.SlipWindow;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * [ LBLD ] 普通人都能做出来
 *
 * 01234567
 * eidbacoo - abc
 * rrrr
 * l
 *     r4
 *  l1
 *      r5
 *   l2
 *       r6
 *    l3
 *        r7
 *     l4
 *         r8(over)
 *
 *
 * 0 1 2 3 4 5 6 7
 * e i d b o a o o - ab
 * r r r)
 * l l
 *       r
 *   l(判id)
 *     l
 *        r
 *     l(判db)
 *
 *
 * -> 思路：
 *      定长滑动窗口 每次左右动1
 */

/**
 * [自己思路] 别人也写不对!! (直接放弃)
 *
 * *** 自己的想法，并不庞大，但不要脑想，一定注释中敲一下
 *
 * 0 1 2 3 4 5 6 7
 * e i d b o a o o - ab
 * r r r r r r
 *
 *
 * 0 1 2 3 4 5 6 7
 * e i d b a c o o - abc
 * r r r r r r (ifcur是abc back con +1， else =0) -> tar每个元素可能多个 要用map ifcur是abc map+1 else map=tmp的cur+1
 *             r
 *             w (curConlen=3) -> 直接收集res
 *         l=6-2 (注：l只动1个，因为有可能是 bacb)
 *
 * --> 这种我的'旧时代'思路 一看就不对 太精细了
 *
 * [深拷贝 浅拷贝]
 *  // windowMapTmp = windowMap; //对象引用拷贝不能用=
 *  /*
 *          无论是 windowMapTmp.putAll(windowMap);
 *          还是 for重新赋值
 *          因为你 Character 是 String 常量，永远不能new新的，所以key还会定义到1个，
 *          map 和 mapTmp 的 entry桶 指向的是同一个
 *
 *          -> 所以 无法实现 key=string/char 的 map 的 重置 ？
 */

/**
 * 【近期精华大总结】
 *      1 先 汉 整 架 （先写后面的 代码 是 正确的）
 *      2 脑想蒙蔽 -> 立刻 注释敲
 *
 * [本题精华]
 *  0 l为什么必须 *后* map-1 -> 脑干想蒙蔽 -> 立刻 注释敲
 *  1 定长滑动窗口 每次左右动1
 *  2 我理所当然 的 ’太精细想法‘ -> 直接放弃 （别人也写不对）
 *  3 框架思想：
 *      r只负责+ l只负责-
 *  4 当 bbba ->缩到 ba 时 ,  此时 eq 才 valid-1
 */

public class 字符串排列567 {

//    /*
//     [自] 实现不了 -> map 对象套enter对象 copy重置不了
//     */
//    // wM中每个元素个数<=nM 当前cur是tar中1个
//    boolean thisMixCondtion(Map<Character, Integer> windowMap, Map<Character, Integer> needMap, char cur) {
//        // wM中每个元素个数<=nM
//        //(needMap 为核心)
//        for (char c : needMap.keySet()) {
//            if (windowMap.get(c) > needMap.get(c)) {
//                return false;
//            }
//        }
//        // 当前cur是tar中1个
//        if (!needMap.keySet().contains(cur)) {
//            return false;
//        } else {
//            // map清0
//            windowMap = windowMapTmp;
//        }
//        return true;
//    }
//    boolean isNumEq(Map<Character, Integer> windowMap, Map<Character, Integer> needMap) {
//        // wM中每个元素个数<=nM
//        //(needMap 为核心)
//        for (char c : needMap.keySet()) {
//            if (!windowMap.get(c).equals(needMap.get(c))) {
//                return false;
//            }
//        }
//        return true;
//    }
//    // 加入后不超
//    boolean isAfterAddDontOver(Map<Character, Integer> windowMap, Map<Character, Integer> needMap, char cur) {
//        windowMap.put(cur, windowMap.get(cur) + 1);
//        for (char c : needMap.keySet()) { // *** 核心：能用needMap就用needMap
//            if (windowMap.get(c) > needMap.get(c)) {
//                windowMap.put(cur, windowMap.get(cur) - 1); // 还原
//                return false;
//            }
//        }
//        return true;
//    }
//    HashMap<Character, Integer> windowMapTmp = null ;
//    public boolean checkInclusion2(String s, String need) {
//        HashMap<Character, Integer> needMap = new HashMap<>(), windowMap = new HashMap<>();
//        for (char c : need.toCharArray()) {
//            needMap.put(c, needMap.getOrDefault(c, 0) + 1);
//        }
//        for (char c : s.toCharArray()) {
//            windowMap.put(c, 0);
//        }
//        int left = 0, right = 0;
//        int valid = 0;
//
//        // windowMapTmp = windowMap; //对象引用拷贝不能用=
//        /*
//         无论是 windowMapTmp.putAll(windowMap);
//         还是 for重新赋值
//         因为你 Character 是 String 常量，永远不能new新的，所以key还会定义到1个，
//         map 和 mapTmp 的 entry桶 指向的是同一个
//
//         -> 所以 无法实现 key=string/char 的 map 的 重置 ？
//         */
//        windowMapTmp = (HashMap<Character, Integer>)windowMap.clone();
//
//        List<String> res = new ArrayList<>();
//
//        while (right < s.length()) {
//            // c 是将移入窗口的字符
//            char curRight = s.charAt(right);
//            // 右移窗口
//            right++;
//            // 进行窗口内数据的一系列更新
//            // * 更新windowMap
//            // wM中每个元素个数<=nM 当前cur是tar中1个 加入后不超(字串要完全个数一致) 超了不变x
//            /**
//             * e b a b c e f  - abc
//             * r r r r
//             * -> beb bab 如何判断留不留上一个a e
//             * 答 e有map重新初始化tmp
//             *   bab 因为连续的con有效，所以新b不+1即可
//             */
//            if(!needMap.containsKey(curRight)) {
//                // 如果当前这个 不con tar -> map复原tmp
//                windowMap = (HashMap<Character, Integer>) windowMapTmp;
//            } else {
//                if (thisMixCondtion(windowMap, needMap, curRight)) {
//                    isAfterAddDontOver(windowMap, needMap, curRight);
//                }
//            }
//
//            /*** debug 输出的位置 ***/
//            System.out.println(String.format("window: [%d, %d)\n", left, right));
//            /********************/
//
//            // 判断左侧窗口是否要收缩
//            if (isNumEq(windowMap, needMap)) {
//                //收集
//                System.out.println("-"+s.substring(right - need.length(), right));
//                res.add(s.substring(right - need.length(), right));
//                // 最头那个num-1
//                char finalLeftChar = s.charAt(s.charAt(right - need.length()));
//                windowMap.put(finalLeftChar, windowMap.get(finalLeftChar)-1);
//                //l=r-size+1
//                left = right - need.length() + 1;
//            }
//        }
//        return !res.isEmpty();
//    }
//
//    /*
//     [LBLD] 定长 1 滑窗
//
//      0 1 2 3 4 - abc
//      b b b c a
//      r r r r(v=1)
//        l(v这里 b=1 != 3 ，我-1了 不该-1 !) --妙改--> b=1 b刚好剩==ned中b的个数 时，才-1
//              r
//          l     r(r最终超一个)
//
//     总结：
//        1. 框架思想
//             r只负责+ l只负责-
//        2。当 bbba ->缩到 ba 时 , 当前 leftchar 正好是 num = need个数
//           ** 此时 eq 才 valid-1 （因为 r l 都是 cur落后于++ ）
//
//     */
//    /**
//     *  0 1 2 3 4 - abc
//     *  b b b c a
//     *  r r) map b=1个 之后判valid -> 先放入right 再判断 理所应当！
//     *    r r) b=2 v=1
//     *
//     * 奇怪的是：l为什么必须 后 map-1
//     *      r r) b=3 v=2
//     *  l 先判断 此时[b b b] ,之后再-1
//     */
//    public boolean checkInclusion(String s, String need) {
//        Map<Character, Integer> needMap = new HashMap<>(), windowMap = new HashMap<>();
//        for(char c : need.toCharArray()) {
//            needMap.put(c, needMap.getOrDefault(c, 0)+1);
//        }
//        for(char c: s.toCharArray()) {
//            windowMap.put(c, 0);
//        }
//        int left = 0, right = 0, valid = 0;
//
//        while (right < s.length()) {
//            char rc = s.charAt(right);
//            right++;
//            if (needMap.containsKey(rc)) {
//                windowMap.put(rc, windowMap.get(rc)+1);
//                if(windowMap.get(rc).equals(needMap.get(rc))) {
//                    valid ++ ; // r 只负责 扩 +
//                }
//            }
//
//            // r-l 看 个数
//            while (right - left == need.length()) {
//                // valid 看 种类
//                if (valid == needMap.keySet().size()) {
//                    return true;
//                }
//
//                char lc = s.charAt(left);
//                left++;
//                if(needMap.containsKey(lc)) {
//                    if(windowMap.get(lc).equals(needMap.get(lc))) { // 只判断 当前1个 即可
//                        valid -- ; // l 只负责 缩 -
//                    }
//                    windowMap.put(lc, windowMap.get(lc)-1);
//                }
//            }
//        }
//        return false;
//    }
//
//    @Test
//    public void test(){
//        String s= "ab" ,s2 = "eidbaooo";
//        // System.out.println(checkInclusion(s2,s));
//        /**
//         * 0 1 2 3 4 - abc
//         * b b b c a
//         * r r r r(v=1)
//         *   l(v这里 b=1 != 3 ，我-1了 不该-1 !) --妙改--> b=1 b刚好剩==ned中b的个数 时，才-1
//         *         r
//         *     l     r(r最终超一个)
//         *
//         */
//        System.out.println(checkInclusion("bbbca","abc"));
//    }
}
